#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1000, MAXM = 1000000, INF = 10001000;
int n = 9, m = 28; // |V|=n, |E|=m
int u[MAXM] = {0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 ,1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 };
int v[MAXM] = {1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 ,0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 };
int w[MAXM] = {4,8,11,8,7,1,2,6,7,4,2,14,9,10,4,8,11,8,7,1,2,6,7,4,2,14,9,10};
int d[MAXN];

void Bellman_Ford() {
    for (int i = 0; i < n; ++i) d[i] = INF;
    d[0] = 0;
    for (int k = 0; k < n - 1; ++k) for (int i = 0; i < m; ++i) {
        int x = u[i], y = v[i];
        if (d[x] < INF) d[y] = min(d[y], d[x] + w[i]);
    }
}

int main() {
    Bellman_Ford();
    for (int i = 0; i < n; ++i) cout << d[i] << ' ';
    cout << endl;
}

